package leetcode.D2000.T1254;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-02-26 12:50:39 星期六
 */
class Solution {
    private static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int closedIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, num = 0;
        for(int i=0; i<m; ++i) {
            dfs(grid, i, 0);
            dfs(grid, i, n-1);
        }
        for(int j=0; j<n; ++j) {
            dfs(grid, 0, j);
            dfs(grid, m-1, j);
        }
        for(int i=1; i<m-1; ++i) {
            for(int j=1; j<n-1; ++j) {
                if (grid[i][j]==0) {
                    num++;
                    dfs(grid, i, j);
                }
            }
        }
        return num;
    }
    private void dfs(int[][] grid, int row, int col) {
        if (grid[row][col] == 1)
            return;
        grid[row][col] = 1;
        for (int[] dir : dirs) {
            int x = row+dir[0], y = col+dir[1], m = grid.length, n = grid[0].length;
            if(x>=0 && x<m && y>=0 && y<n)
                dfs(grid, x, y);
        }
    }
}
